//剑指offfer题4：输入某二叉树的前序遍历和中序遍历的结果，重建该二叉树。
//    思路一：递归             思路二：非递归
#include<iostream>
using namespace std;
#include<vector>
struct TreeNode
{
	int val;
	TreeNode *left;
	TreeNode *right;
	TreeNode(const int x) :val(x), left(0), right(0){}
};
TreeNode *ReConstructBinaryTree(vector<int> pre, vector<int> vin)
{
	if (pre.empty())return NULL;
	vector<int> leftpre; vector<int> rightpre;
	vector<int> leftvin; vector<int> rightvin;
	int i = 0, j = 0;
	TreeNode *root = new TreeNode(pre[i++]);
	while (pre[0] != vin[j++])
	{
		leftpre.push_back(pre[i++]);
		leftvin.push_back(vin[j - 1]);
	}
	while (i < pre.size())
	{
		rightpre.push_back(pre[i++]);
		rightvin.push_back(vin[j++]);
	}
	root->left = ReConstructBinaryTree(leftpre, leftvin);
	root->right = ReConstructBinaryTree(rightpre, rightvin);
	return root;
}
int main()
{
	int index = 0;
	int arr1[] = { 1, 2, 4, 7, 3, 5, 6, 8 };
	int arr2[] = { 4, 7, 2, 1, 5, 3, 8, 6 };
	vector<int> pre;
	for(index = 0;index < sizeof(arr1) / sizeof(arr1[0]);++index)
		pre.push_back(arr1[index]);
	vector<int> vin;
	for(index = 0;index < sizeof(arr2) / sizeof(arr2[0]);++index)
		vin.push_back(arr2[index]);

	TreeNode *root;
	root = ReConstructBinaryTree(pre, vin);//递归方法             非递归方法没写
	cout << "由前序和中序重建" << endl;

	return 0;
}
